1151. Minimum Swaps to Group All 1's Together
Medium

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.

 

Example 1:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: 
There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

Example 2:

Input: data = [0,0,0,1,0]
Output: 0
Explanation: 
Since there is only one 1 in the array, no swaps needed.

Example 3:

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation: 
One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].

Example 4:

Input: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1]
Output: 8

 

Constraints:

  • 1 <= data.length <= 105
  • data[i] is 0 or 1.
Accepted
17,318
Submissions
29,335
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
How many 1's should be grouped together ? Is not a fixed number?
Show Hint 2
Yeah it's just the number of 1's the whole array has. Let's name this number as ones
Show Hint 3
Every subarray of size of ones, needs some number of swaps to reach, Can you find the number of swaps needed to group all 1's in this subarray?
Show Hint 4
It's the number of zeros in that subarray.
Show Hint 5
Do you need to count the number of zeros all over again for every position ?
Show Hint 6
Use Sliding Window technique.

Average Rating: 4.82 (22 votes)

Premium

Video Solution


 

Solution Article


Overview

Assuming that there are ones 1's in the input array data, we need to find a subarray, or a window, of length ones and put all 1's in it by swapping 0's out. Therefore, among all windows of length ones, to find the minimum number of swaps required, we need to find the maximum number of 1's in the window so that we can make the smallest number of swaps to achieve the goal.

Swapping 0's and 1's

Figure 1. Find a subarray of length ones and swapping 0's with 1's.



Approach 1: Sliding Window with Two Pointers

Algorithm

We will use two pointers left and right to maintain a sliding window of length ones, and while we check every window through the input array data, we would calculate the number of 1's in it as cnt_one and store the largest one as max_one.

While the window is sliding through data, we want to maintain its length as ones. At the same time, we also want to update the number of 1's in the window by adding the new boundary data[right] and deducting the left boundary data[left].

Current
1 / 5

Complexity Analysis

  • Time complexity: O(n)\mathcal{O}(n), when nn is the length of the array.
  • Space complexity: O(1)\mathcal{O}(1).

Approach 2: Sliding Window with Deque (Double-ended Queue)

Algorithm

An alternative way to implement the sliding window algorithm is to use Deque (Double-ended Queue). The key idea is to maintain a deque deque with the size of ones by adding new elements to its right end and popping old elements from its left end.

More specifically speaking, after initializing deque, we would start appending elements to its right before its size reaches ones. When there are ones elements in deque, we keep appending new elements to its right, and we would also remove the leftmost element from it so that its size is always ones. Along this process, we can perform counting the number of 1's in this deque which is similar to Approach 1.

Complexity Analysis

  • Time complexity: O(n)\mathcal{O}(n), when nn is the length of the array. Note that the time complexities of adding the element to deque's right end and popping the element from its left end are both O(1)\mathcal{O}(1).
  • Space complexity: O(n)\mathcal{O}(n), when nn is the length of the array. This is because we need a Deque of size ones.

Report Article Issue

Comments: 12
jiangjhcj's avatar
Read More

I think the hints are unnecessarily cryptic because they are not complete sentences. They are written like Kevin from the Office when he tried to save time by omitting some words from a sentence.

50
Show 2 replies
Reply
Share
Report
code-box's avatar
Read More

I really like the explanation in this article. Initially, I thought it would going to be tough. But it's more about the maths behind it.

7
Reply
Share
Report
askramana's avatar
Read More

Java, sliding window O(n) solution

class Solution {
    public int minSwaps(int[] data) {
        // `ones` will also serve as the size for our sliding window
        int ones = Arrays.stream(data).sum();
        
        int runningOnes = 0;
        // Count 1s in first `ones` elements
        for (int i = 0; i < ones; i++) {
            runningOnes += data[i];
        }
        int swapsRequired = ones - runningOnes;
        for (int i = ones; i < data.length; i++) {
            // Drop leftmost from sliding window, and accumulate next right
            runningOnes = runningOnes - data[i-ones] + data[I];
            // runningOnes holds 1s seen in current window
            swapsRequired = Math.min(swapsRequired, ones - runningOnes);
        }
        return swapsRequired;
    }
}

3
Reply
Share
Report
NickSchmitt's avatar
Read More

Great video. Thanks.

1
Reply
Share
Report
florin5's avatar
Read More

The solution 2 consumes more space but doesn't add benefits. It is useful just to show there are alternatives, but not good alternatives :-)

1
Show 3 replies
Reply
Share
Report
lenchen1112's avatar
Read More

One pointer only:

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        window = data.count(1)
        zeros, ans = 0, float('inf')
        for i, d in enumerate(data):
            if d == 0: zeros += 1
            if i >= window - 1:
                if i >= window and data[i - window] == 0:
                    zeros -= 1
                ans = min(ans, zeros)
        return ans

0
Reply
Share
Report
sriharik's avatar
Read More

Basically the idea is we want to create a window of however many ones there are in the array. We assume a certain substring contains all ones. If we assume everything to be ones within our sliding window (without actually changing the value) the number of swaps will be equal to the total number of 1s subtracted with the number of 1s inside our sliding window. We care about the ones outside our sliding window since those values will have to be swapped to zeros. The values that are alread zero outside the window do not matter. Its a unique case where we care about things outside our window instead of inside it. Don't let it trip you up.

 public int minSwaps(int[] data) {
        int totalOnes = 0, totalZeros = 0;
        for (int i = 0; i < data.length; i++) {
            if (data[i] == 1) totalOnes++;
            else totalZeros++;
        }
        if (totalOnes == 1) return 0;
        
        int right = totalOnes - 1, left = 0, min = Integer.MAX_VALUE, localOnes = 0, localZeros = 0;
        
        for (int i = 0; i < totalOnes; i++) {
            if (data[i] == 0) localZeros++;
            else localOnes++;
        }
                
        while (right < data.length) {
            int onesOutSideWindow = totalOnes - localOnes;
            min = Math.min(onesOutSideWindow, min);
            
            if (right + 1 >= data.length) break;
            
            if (data[++right] == 0) localZeros++;
            else localOnes++;
            
            if (data[left++] == 1) localOnes--;
            else localZeros--;
        }

        return min;
    }

0
Reply
Share
Report
yi64's avatar
Read More

What's the underlying math support here? The intuition is that the minimum swaps of each subarray window equals to the number of zeros. This is not always true. E.g. [1, 0, 0, 1, 1]. For the first subarray window "[1, 0, 0]", the minimum number of swaps is two as we have two 0s here. But it is actually one as we can swap "0, 0" with "1, 1" through one swap.

0
Show 1 reply
Reply
Share
Report
mehakwaliaC's avatar
Read More

This is the prefix sum solution using the sliding window method.

int minSwaps(vector<int>& data) {
        vector<int> pf(data.size());
        partial_sum(data.begin(), data.end(), pf.begin());
        pf.insert(pf.begin(), 0);
        int ones = pf.back();
        int j=ones; int i=0;
        int max_ones=INT_MIN;
        while (j<pf.size()){
            max_ones=max(max_ones, pf[j]-pf[i]);
            i++; j++;
        }
        return ones-max_ones;
    }

0
Reply
Share
Report
hitzy's avatar
Read More

First count ones, fill a window of ones and swaps needed (zeros need to be swapped out) and then keep sliding window and compute minSwap:

class Solution {
    public int minSwaps(int[] data) {
        if (data == null || data.length < 2) return 0;
        int ones = 0;
        for (int i = 0; i < data.length; i++) {
            if (data[i] == 1) ones++;
        }
        int swaps = 0;
        for (int i = 0; i < ones; i++) {
            if (data[i] == 0) swaps++;
        }
        int res = data.length-ones;
        for (int i = ones; i < data.length; i++) {
            res = Math.min(res, swaps);
            if (data[i-ones] == 0) swaps--;
            if (data[i] == 0) swaps++;
        }
        res = Math.min(res, swaps);
        return res;
    }
}

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.